public class question_41 {
}
class Solution_41 {
    public int firstMissingPositive(int[] nums) {
        boolean no_one=true;

        //第一步，把0和负数变成1，
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==1){
                no_one=false;
            }
            if(nums[i]<=0){
                nums[i]=1;
            }
//            大于length的也要变成1，因为这些必然不是目标值，不变成1的话，后面遍历的时候会出现数组越界的问题
            if(nums[i]>0&&nums[i]>nums.length){
                nums[i]=1;
            }
        }
        if(no_one){
            return 1;
        }
        for (int i = 0; i < nums.length; i++) {
            int temp=Math.abs(nums[i]);
            nums[temp-1]=nums[temp-1]>0?-nums[temp-1]:nums[temp-1];
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                return i+1;
            }
        }
        return  nums.length+1;

    }
}
